//二叉排序树

#pragma once

//二叉排序树类型定义
template <typename E>
struct BSTNode
{
    E data;
    BSTNode *lchild, *rchild;
};

template <typename E>
using BSTree = BSTNode<E>*;


//二叉排序树的算法

//最小元素
//若找到，则返回指向最小元素结点的指针
//否则，返回空指针
template <typename E>
BSTree<E> FindMin(BSTree<E> T)
{
    if(T == nullptr) return nullptr;

    auto p = T;
    while (p->lchild)
        p = p->lchild;
    return p;
}

//最大元素
template <typename E>
BSTree<E> FindMax(BSTree<E> T)
{
    if(T == nullptr)
        return nullptr;

    auto p = T;
    while (p->rchild)
        p = p->rchild;
    return p;
}

//在二叉排序 T 中查找元素(递归算法)
//若找到，返回指向该点的指针
//否则，返回空指针
template <typename E>
BSTree<E> SearchBST(BSTree<E> T, E e)
{
    if(T==nullptr) 
        return nullptr;
    if(T->data == e) 
        return T;
    else if(e < T->data)
        return SearchBST(T->lchild, e);
    else
        return SearchBST(T->rchild, e);
}

//查找元素(非递归算法)
template <typename E>
BSTree<E> Search(BSTree<E> T, E e)
{
    auto p = T;
    while(p &&p->data != e){
        p = (e < p->data) ? p->lchild : p->rchild;
        //if(e < p->data)
        //    p = p->lchild;
        //else
        //    p = p->rchild
    }

    return p;   
}

//插入元素(递归元素)
//在二叉排序树 T 中插入数据元素 e
//若元素 e 已经存在，则不再插入
//返回 e 所在结点指针
template <typename E>
BSTree<E> InsertBST(BSTree<E> &T, E e)
{  
    //若二叉树为空，则
    if(T == nullptr){ //若二叉树为空
        //T = new BSTNode<E>;
        //T->data = e;
        //T->lchild = T->rchild = nullptr;
        T = new BSTNode<E> (e, nullptr, nullptr); //插入结点作为根结点
        return T;
    }
    else if(e < T->data){               //若待插入元素 e 小于根结点
        return InsertBST(T->lchild, e); //继续在左子树上插入
    }
    else if(e > T->data){               //若待插入元素 e 大于根结点
        return InsertBST(T->rchild, e); //继续在右子树上插入
    }
    else{                               //若待插入元素 e 等于根结点
        return T;                       //直接返回根结点
    }
}

//插入元素(非递归元素)
template <typename E>
BSTree<E> Insert(BSTree<E> &T, E e)
{
    //查找元素 e 以及其双亲 f
    BSTree<E> p, f;
    p = T, f = nullptr;
    while(p && p->data != e)
        if(e < p->data){
            f = p; p = p->lchild;
        }else{ 
            f = p; p = p->rchild;
        }

    //若找到 e，则直接返回
    if(p)
        return p;

    //否则未找到 e，则插入新结点作为 f 的孩子
    auto s = new BSTNode<E> {e, nullptr, nullptr};
    if(f == nullptr)  // T 为空
        T = s;  //新结点作为根结点
    else if(e < f->data)
        f->lchild = s; // s 作为 f 的左孩子
    else
        f->rchild = s; // s 作为 f 的右孩子
    return s; //返回新建结点 s 
}

//删除元素(递归元素)
//在二叉排序树 T 中删除元素 e 所在的结点
//若元素 e 不存在，则不做任何操作
//最后，若删除成功则返回 true
template <typename E>
bool DeleteBST(BSTree<E> &T, E e)
{
    //递归停止条件：二叉树为空，返回 false
    if(T == nullptr) 
        return false;
    //若 e 在 T 的左子树，则继续在左子树删除
    else if(e < T->data)
        return DeleteBST(T->lchild, e);
    //若 e 在 T 的右子树，则继续在右子树删除
    else if(e > T->data)
        return DeleteBST(T->rchild, e);
    //若 e 等于根结点 T->data,则删除 T
    //(分情况：左右子树均不空，至少有一个子树为空)
    //若 T 的左右子树均不空
    else if(T->lchild && T->rchild){
        //用 T 的左子树上最大元素，替换 T->data
        T->data = FindMax(T->lchild)->data;
        //在 T 的左子树上删除该最大元素
        return DeleteBST(T->lchild, T->data);
    }
    //T 的左右子树至少有一个为空
    else{
        auto p = T; //待删除的结点
        T = T->lchild ? T->lchild : T->rchild;
        delete p;
        return true;
    }
}